/**
 * 53. 最大子序和
 * 
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 
 * 示例 1：
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 
 * 示例 2：
 * 输入：nums = [1]
 * 输出：1
 * 
 * 示例 3：
 * 输入：nums = [0]
 * 输出：0
 * 
 * 示例 4：
 * 输入：nums = [-1]
 * 输出：-1
 * 
 * 示例 5：
 * 输入：nums = [-100000]
 * 输出：-100000
 * 
 * 提示：
 * 1 <= nums.length <= 3 * 10^4
 * -10^5 <= nums[i] <= 10^5
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 */
package zw;

public class T53 {
	// 动态规划
	public int maxSubArray(int[] nums) {
		int dp = nums[0];
		int ans = dp;
		for(int i = 1; i < nums.length; i++) {
			dp = dp + nums[i] > nums[i] ? dp + nums[i] : nums[i];
			ans = ans > dp ? ans : dp;
		}
		return ans;
    }
	
	public static void main(String[] args) {
		T53 t53 = new T53();
		System.out.println(t53.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
	}
}
